//34.在排序数组中查找元素的第一个和最后一个位置

//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//如果数组中不存在目标值 target，返回[-1, -1]。
//你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

//class Solution {
//    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
//    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
//    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
//    int lower_bound(vector<int>& nums, int target) {
//        int left = 0, right = (int)nums.size() - 1; // 闭区间 [left, right]
//        while (left <= right) { // 区间不为空
//            // 循环不变量：
//            // nums[left-1] < target
//            // nums[right+1] >= target
//            int mid = left + (right - left) / 2;
//            if (nums[mid] >= target) {
//                right = mid - 1; // 范围缩小到 [left, mid-1]
//            }
//            else {
//                left = mid + 1; // 范围缩小到 [mid+1, right]
//            }
//        }
//        // 循环结束后 left = right+1
//        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
//        // 所以 left 就是第一个 >= target 的元素下标
//        return left;
//    }
//
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        int start = lower_bound(nums, target);
//        if (start == nums.size() || nums[start] != target) {
//            return { -1, -1 }; // nums 中没有 target
//        }
//        // 如果 start 存在，那么 end 必定存在
//        int end = lower_bound(nums, target + 1) - 1;
//        return { start, end };
//    }
//};
//
//// class Solution {
//// public:
////     vector<int> searchRange(vector<int>& nums, int target) {
////         auto [start, end] = ranges::equal_range(nums, target);
////         if (start == end) {
////             return {-1, -1};
////         }
////         return {(int) (start - nums.begin()), (int) (end - nums.begin() - 1)};
////     }
//// };

//35.搜索插入位置

//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//请必须使用时间复杂度为 O(log n) 的算法。

//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target) {
//        int l = 0, r = nums.size() - 1, mid{};
//        while (l <= r) {
//            mid = l + (r - l) / 2;
//            if (nums[mid] < target) {
//                l = mid + 1;
//            }
//            else {
//                r = mid - 1;
//            }
//        }
//        return l;
//    }
//};

//704.二分查找

//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 - 1。
//你必须编写一个具有 O(log n) 时间复杂度的算法。

//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int l = 0, r = nums.size() - 1, mid{};
//        if (nums[l] > target || nums[r] < target) {
//            return -1;
//        }
//        while (l <= r) {
//            mid = l + (r - l) / 2;
//            nums[mid] < target ? l = mid + 1 : r = mid - 1;
//        }
//        return nums[l] == target ? l : -1;
//    }
//};

//744.寻找比目标字母大的最小字母

//给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。
//返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

//class Solution {
//public:
//    char nextGreatestLetter(vector<char>& letters, char target) {
//        int n = letters.size();
//        if (letters[n - 1] <= target) {
//            return letters[0];
//        }
//        int l = 0, r = n - 1, mid{};
//        while (l <= r) {
//            mid = l + (r - l) / 2;
//            letters[mid] <= target ? l = mid + 1 : r = mid - 1;
//        }
//        return letters[l];
//    }
//};

//2529.正整数和负整数的最大计数

//给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
//换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
//注意：0 既不是正整数也不是负整数。

//class Solution {
//public:
//    int maximumCount(vector<int>& nums) {
//        int n = nums.size(), l = 0, r = n - 1, mid{};
//        if (nums[l] == nums[r] || nums[l] > 0 || nums[r] < 0) {
//            return !nums[l] ? 0 : n;
//        }
//        while (l < r) {
//            mid = l + (r - l) / 2;
//            nums[mid] < 0 ? l = mid + 1 : r = mid;
//        }
//        r = l;
//        while (r < n - 1 && nums[r] == 0) {
//            r++;
//        }
//        return max(l, n - r);
//    }
//};

//2300.咒语和药水的成功对数

//给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
//同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
//请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

//class Solution {
//public:
//    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
//        int n = potions.size(), l{}, r{}, mid{};
//        ranges::sort(potions);
//        for (int& s : spells) {
//            long long target = (success - 1) / s;
//            if (potions.back() > target) {
//                l = 0;
//                r = n;
//                while (l < r) {
//                    mid = l + (r - l) / 2;
//                    potions[mid] > target ? r = mid : l = mid + 1;
//                }
//                s = n - l;
//            }
//            else {
//                s = 0;
//            }
//        }
//        return spells;
//    }
//};

//1385.两个数组间的距离值

//给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
//「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 | arr1[i] - arr2[j]| <= d 。

//class Solution {
//public:
//    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
//        ranges::sort(arr2);
//        int ans = arr1.size(), n = arr2.size(), l = 0, r = n, mid{};
//        for (int x : arr1) {
//            while (l <= r) {
//                mid = l + (r - l) / 2;
//                if (x - arr2[mid] > d) {
//                    l = mid + 1;
//                }
//                else if (x - arr2[mid] < -d) {
//                    r = mid - 1;
//                }
//                else {
//                    ans--;
//                    break;
//                }
//            }
//            l = 0;
//            r = n;
//        }
//        return ans;
//    }
//};

//2389.和有限的最长子序列

//给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
//返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
//子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

//class Solution {
//public:
//    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
//        ranges::sort(nums);
//        int n = nums.size();
//        for (int i = 1; i < n; i++) {
//            nums[i] += nums[i - 1];
//        }
//        for (int& q : queries) {
//            int l = 0, r = n - 1, mid{};
//            while (l <= r) {
//                mid = l + (r - l) / 2;
//                nums[mid] <= q ? l = mid + 1 : r = mid - 1;
//            }
//            q = l;
//        }
//        return queries;
//    }
//};

//1170.比较字符串最小字母出现频次

//定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。
//例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
//现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
//请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

//class Solution {
//public:
//    int f(string s) {
//        int ans = 0;
//        char t = s[0];
//        for (char c : s) {
//            if (c < t) {
//                ans = 0;
//                t = c;
//            }
//            if (c == t) {
//                ans++;
//            }
//        }
//        return ans;
//    }
//
//    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
//        int n = words.size(), l = 0, r = n, mid{}, m = queries.size();
//        vector<int> ans(m), tmp;
//        for (string w : words) {
//            tmp.emplace_back(f(w));
//        }
//        ranges::sort(tmp);
//        for (int i = 0; i < m; i++) {
//            int q = f(queries[i]);
//            while (l < r) {
//                mid = l + (r - l) / 2;
//                tmp[mid] <= q ? l = mid + 1 : r = mid;
//            }
//            ans[i] = n - l;
//            l = 0;
//            r = n;
//        }
//        return ans;
//    }
//};

//2080.区间内查询数字的频率

//请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
//子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
//请你实现 RangeFreqQuery 类：
//RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
//int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
//一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

//class RangeFreqQuery {
//    unordered_map<int, vector<int>> pos;
//
//public:
//    RangeFreqQuery(vector<int>& arr) {
//        for (int i = 0; i < arr.size(); i++) {
//            pos[arr[i]].push_back(i);
//        }
//    }
//
//    int query(int left, int right, int value) {
//        // 不推荐写 a = pos[value]，如果 value 不在 pos 中会插入 value
//        auto it = pos.find(value);
//        if (it == pos.end()) {
//            return 0;
//        }
//        auto& a = it->second;
//        return ranges::upper_bound(a, right) - ranges::lower_bound(a, left);
//    }
//};
//
///**
// * Your RangeFreqQuery object will be instantiated and called as such:
// * RangeFreqQuery* obj = new RangeFreqQuery(arr);
// * int param_1 = obj->query(left,right,value);
// */

//3488.距离最小相等元素查询

//给你一个 环形 数组 nums 和一个数组 queries 。
//对于每个查询 i ，你需要找到以下内容：
//数组 nums 中下标 queries[i] 处的元素与 任意 其他下标 j（满足 nums[j] == nums[queries[i]]）之间的 最小 距离。如果不存在这样的下标 j，则该查询的结果为 - 1 。
//返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

//class Solution {
//public:
//    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
//        unordered_map<int, vector<int>> indexs;
//        int n = nums.size();
//        for (int i = 0; i < n; i++) {
//            indexs[nums[i]].emplace_back(i);
//        }
//
//        for (auto& [_, p] : indexs) {
//            int t = p[0];
//            p.insert(p.begin(), p.back() - n);
//            p.emplace_back(t + n);
//        }
//
//        for (int& q : queries) {
//            auto& p = indexs[nums[q]];
//            if (p.size() == 3) {
//                q = -1;
//            }
//            else {
//                int t = ranges::lower_bound(p, q) - p.begin();
//                q = min(q - p[t - 1], p[t + 1] - q);
//            }
//        }
//        return queries;
//    }
//};

//2563.统计公平数对的数目

//给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
//如果(i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
//0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper

//class Solution {
//public:
//    long long countFairPairs(vector<int>& nums, int lower, int upper) {
//        ranges::sort(nums);
//        long long ans = 0;
//        for (int j = 0; j < nums.size(); j++) {
//            auto r = upper_bound(nums.begin(), nums.begin() + j, upper - nums[j]);
//            auto l = lower_bound(nums.begin(), nums.begin() + j, lower - nums[j]);
//            ans += r - l;
//        }
//        return ans;
//    }
//};

//2070.每一个查询的最大美丽值

//给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。
//同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。
//如果不存在符合条件的物品，那么查询的结果为 0 。
//请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

//class Solution {
//public:
//    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
//        ranges::sort(items, {}, [](auto& item) { return item[0]; });
//        for (int i = 1; i < items.size(); i++) {
//            items[i][1] = max(items[i][1], items[i - 1][1]);
//        }
//
//        for (int& q : queries) {
//            int j = ranges::upper_bound(items, q, {}, [](auto& item) { return item[0]; }) - items.begin();
//            q = j ? items[j - 1][1] : 0;
//        }
//        return queries;
//    }
//};

//1146.快照数组

//实现支持下列接口的「快照数组」 - SnapshotArray：
//SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
//void set(index, val) - 会将指定索引 index 处的元素设置为 val。
//int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
//int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

//class SnapshotArray {
//    unordered_map<int, vector<pair<int, int>>> history;
//    int cur_snap_id = 0;
//
//public:
//    SnapshotArray(int) {}
//
//    void set(int index, int val) {
//        history[index].emplace_back(cur_snap_id, val);
//    }
//
//    int snap() {
//        return cur_snap_id++;
//    }
//
//    int get(int index, int snap_id) {
//        auto& h = history[index];
//        int j = ranges::lower_bound(h, pair(snap_id + 1, 0)) - h.begin() - 1;
//        return j >= 0 ? h[j].second : 0;
//    }
//};
///**
// * Your SnapshotArray object will be instantiated and called as such:
// * SnapshotArray* obj = new SnapshotArray(length);
// * obj->set(index,val);
// * int param_2 = obj->snap();
// * int param_3 = obj->get(index,snap_id);
// */

//981.基于时间的键值存储

//设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
//实现 TimeMap 类：
//TimeMap() 初始化数据结构对象
//void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
//String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。
//如果有多个这样的值，它将返回与最大  timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。

//class TimeMap {
//    unordered_map<string, vector<pair<int, string>>> m;
//
//public:
//    TimeMap() {}
//
//    void set(string key, string value, int timestamp) {
//        m[key].emplace_back(timestamp, value);
//    }
//
//    string get(string key, int timestamp) {
//        auto& pairs = m[key];
//        pair<int, string> p = { timestamp, string({127}) };
//        auto i = upper_bound(pairs.begin(), pairs.end(), p);
//        if (i != pairs.begin()) {
//            return (i - 1)->second;
//        }
//        return "";
//    }
//};
//
///**
// * Your TimeMap object will be instantiated and called as such:
// * TimeMap* obj = new TimeMap();
// * obj->set(key,value,timestamp);
// * string param_2 = obj->get(key,timestamp);
// */

//3508.设计路由器

//请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：
//source：生成该数据包的机器的唯一标识符。
//destination：目标机器的唯一标识符。
//timestamp：该数据包到达路由器的时间戳。
//实现 Router 类：
//Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。
//memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。
//如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。
//bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。
//如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
//如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。
//int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。
//从存储中移除该数据包。
//以数组[source, destination, timestamp] 的形式返回该数据包。
//如果没有数据包可以转发，则返回空数组。
//int getCount(int destination, int startTime, int endTime)：
//返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围[startTime, endTime]（包括两端）内的数据包数量。
//注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。

//struct TupleHash {
//    template<typename T>
//    static void hash_combine(size_t& seed, const T& v) {
//        seed ^= hash<T>{}(v)+0x9e3779b9 + (seed << 6) + (seed >> 2);
//    }
//
//    size_t operator()(const tuple<int, int, int>& t) const {
//        auto& [a, b, c] = t;
//        size_t seed = 0;
//        hash_combine(seed, a);
//        hash_combine(seed, b);
//        hash_combine(seed, c);
//        return seed;
//    }
//};
//
//class Router {
//    int memory_limit;
//    queue<tuple<int, int, int>> packet_q;
//    unordered_set<tuple<int, int, int>, TupleHash> packet_set;
//    unordered_map<int, pair<vector<int>, int>> dest_to_timestamps;
//
//public:
//    Router(int memoryLimit) {
//        memory_limit = memoryLimit;
//    }
//
//    bool addPacket(int source, int destination, int timestamp) {
//        auto packet = make_tuple(source, destination, timestamp);
//        if (!packet_set.insert(packet).second) {
//            return false;
//        }
//        if (packet_q.size() == memory_limit) {
//            forwardPacket();
//        }
//        packet_q.push(packet);
//        dest_to_timestamps[destination].first.push_back(timestamp);
//        return true;
//    }
//
//    vector<int> forwardPacket() {
//        if (packet_q.empty()) {
//            return {};
//        }
//        auto packet = packet_q.front();
//        packet_q.pop();
//        packet_set.erase(packet);
//        auto [source, destination, timestamp] = packet;
//        dest_to_timestamps[destination].second++;
//        return { source, destination, timestamp };
//    }
//
//    int getCount(int destination, int startTime, int endTime) {
//        auto& [timestamps, head] = dest_to_timestamps[destination];
//        auto left = ranges::lower_bound(timestamps.begin() + head, timestamps.end(), startTime);
//        auto right = ranges::upper_bound(timestamps.begin() + head, timestamps.end(), endTime);
//        return right - left;
//    }
//};
//
///**
// * Your Router object will be instantiated and called as such:
// * Router* obj = new Router(memoryLimit);
// * bool param_1 = obj->addPacket(source,destination,timestamp);
// * vector<int> param_2 = obj->forwardPacket();
// * int param_3 = obj->getCount(destination,startTime,endTime);
// */

//658.找到 K 个最接近的元素

//给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
//整数 a 比整数 b 更接近 x 需要满足：
//| a - x | < | b - x | 或者
//| a - x| == |b - x | 且 a < b

//class Solution {
//public:
//    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
//        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
//        int left = right - 1;
//        while (k--) {
//            if (left < 0) {
//                right++;
//            }
//            else if (right >= arr.size()) {
//                left--;
//            }
//            else if (x - arr[left] <= arr[right] - x) {
//                left--;
//            }
//            else {
//                right++;
//            }
//        }
//
//        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
//    }
//};

//1818.绝对差值和

//给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
//数组 nums1 和 nums2 的 绝对差值和 定义为所有 | nums1[i] - nums2[i] | （0 <= i < n）的 总和（下标从 0 开始）。
//你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
//在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
//| x | 定义为：
//如果 x >= 0 ，值为 x ，或者
//如果 x <= 0 ，值为 - x

//class Solution {
//public:
//    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums2.size(), mod = 1'000'000'007;
//        vector<int> sorted_nums1(nums1);
//        ranges::sort(sorted_nums1);
//        long long target_sum = 0;
//        int mx_diff = 0;
//        int cur_diff = 0;
//        for (int i = 0; i < n; i++) {
//            cur_diff = abs(nums1[i] - nums2[i]);
//            target_sum += cur_diff;
//            auto it = ranges::lower_bound(sorted_nums1.begin(), sorted_nums1.end(), nums2[i]);
//            if (it != sorted_nums1.end()) {
//                mx_diff = max(mx_diff, cur_diff - abs(sorted_nums1[it - sorted_nums1.begin()] - nums2[i]));
//            }
//            if (it != sorted_nums1.begin()) {
//                mx_diff = max(mx_diff, cur_diff - abs(sorted_nums1[it - sorted_nums1.begin() - 1] - nums2[i]));
//            }
//        }
//        return (target_sum - mx_diff) % mod;
//    }
//};

//911.在线选举

//给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
//对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
//在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
//实现 TopVotedCandidate 类：
//TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
//int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

//class TopVotedCandidate {
//    vector<int> tops;
//    vector<int> times;
//public:
//    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
//        int cnt[5001]{};
//        int top{};
//        for (int p : persons) {
//            cnt[p]++;
//            if (cnt[p] >= cnt[top]) {
//                top = p;
//            }
//            tops.emplace_back(top);
//        }
//        this->times = times;
//    }
//
//    int q(int t) {
//        int pos = ranges::upper_bound(times, t) - times.begin() - 1;
//        return tops[pos];
//    }
//};
//
///**
// * Your TopVotedCandidate object will be instantiated and called as such:
// * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
// * int param_1 = obj->q(t);
// */

//LCP 08.剧情触发时间

//在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。
//在游戏开始时（第 0 天），三种属性的值均为 0。
//随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。
//这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1, 2, 1], [3, 4, 2]] 表示第一天三种属性分别增加 1, 2, 1 而第二天分别增加 3, 4, 2。
//所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，
//对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。
//根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 - 1 。

//class Solution {
//public:
//    vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& r) {
//        inc.insert(begin(inc), { 0, 0, 0 });
//        int n = r.size(), m = inc.size();
//        vector<int> ans(n, -1);
//        for (int i = 1; i < m; ++i) {
//            for (int j = 0; j < 3; ++j) {
//                inc[i][j] += inc[i - 1][j];
//            }
//        }
//        for (int i = 0; i < n; ++i)
//            if (int t = ranges::lower_bound(inc, r[i], [](auto& v, auto& x) {
//                return v[0] < x[0] || v[1] < x[1] || v[2] < x[2];
//                }) - begin(inc); t != m) {
//                ans[i] = t;
//            }
//        return ans;
//    }
//};

//1287.有序数组中出现次数超过 25 % 的元素

//给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25 % 。
//请你找到并返回这个整数

//class Solution {
//public:
//    int findSpecialInteger(vector<int>& arr) {
//        int m = arr.size() / 4;
//        for (int i : {m, m * 2 + 1}) {
//            int x = arr[i];
//            int j = ranges::lower_bound(arr, x) - arr.begin();
//            if (arr[j + m] == x) {
//                return x;
//            }
//        }
//        return arr[m * 3 + 2];
//    }
//};